home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / dkbsrc.zip / CSG.C < prev    next >
C/C++ Source or Header  |  1991-05-04  |  8KB  |  278 lines
  1. /*****************************************************************************
  2. *
  3. *                                    csg.c
  4. *
  5. *   from DKBTrace (c) 1990  David Buck
  6. *
  7. *  This module implements routines for constructive solid geometry.
  8. *
  9. * This software is freely distributable. The source and/or object code may be
  10. * copied or uploaded to communications services so long as this notice remains
  11. * at the top of each file.  If any changes are made to the program, you must
  12. * clearly indicate in the documentation and in the programs startup message
  13. * who it was who made the changes. The documentation should also describe what
  14. * those changes were. This software may not be included in whole or in
  15. * part into any commercial package without the express written consent of the
  16. * author.  It may, however, be included in other public domain or freely
  17. * distributed software so long as the proper credit for the software is given.
  18. *
  19. * This software is provided as is without any guarantees or warranty. Although
  20. * the author has attempted to find and correct any bugs in the software, he
  21. * is not responsible for any damage caused by the use of the software.  The
  22. * author is under no obligation to provide service, corrections, or upgrades
  23. * to this package.
  24. *
  25. * Despite all the legal stuff above, if you do find bugs, I would like to hear
  26. * about them.  Also, if you have any comments or questions, you may contact me
  27. * at the following address:
  28. *
  29. *     David Buck
  30. *     22C Sonnet Cres.
  31. *     Nepean Ontario
  32. *     Canada, K2H 8W7
  33. *
  34. *  I can also be reached on the following bulleton boards:
  35. *
  36. *     OMX              (613) 731-3419
  37. *     Mystic           (613) 596-4249  or  (613) 596-4772
  38. *
  39. *  Fidonet:   1:163/109.9
  40. *  Internet:  dbuck@ccs.carleton.ca
  41. *  The "You Can Call Me RAY" BBS    (708) 358-5611
  42. *
  43. *  IBM Port by Aaron A. Collins. Aaron may be reached on the following BBS'es:
  44. *
  45. *     The "You Can Call Me RAY" BBS (708) 358-5611
  46. *     The Information Exchange BBS  (708) 945-5575
  47. *
  48. *****************************************************************************/
  49.  
  50.  
  51. #include "frame.h"
  52. #include "vector.h"
  53. #include "dkbproto.h"
  54.  
  55. METHODS CSG_Union_Methods =
  56.    { Object_Intersect, All_CSG_Union_Intersections,
  57.      Inside_CSG_Union, NULL,
  58.      Copy_CSG,
  59.      Translate_CSG, Rotate_CSG,
  60.      Scale_CSG, Invert_CSG};
  61.  
  62. METHODS CSG_Intersection_Methods =
  63.    { Object_Intersect, All_CSG_Intersect_Intersections,
  64.      Inside_CSG_Intersection, NULL,
  65.      Copy_CSG,
  66.      Translate_CSG, Rotate_CSG,
  67.      Scale_CSG, Invert_CSG};
  68.  
  69. extern RAY *VP_Ray;
  70. extern unsigned long Options;
  71.  
  72. int All_CSG_Union_Intersections (Object, Ray, Depth_Queue)
  73.    OBJECT *Object;
  74.    RAY *Ray;
  75.    PRIOQ *Depth_Queue;
  76.    {
  77.    register int Intersection_Found;
  78.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  79.    SHAPE *Local_Shape;
  80.  
  81.    Intersection_Found = FALSE;
  82.    for (Local_Shape = Shape -> Shapes;
  83.         Local_Shape != NULL ;
  84.         Local_Shape = Local_Shape -> Next_Object)
  85.  
  86.        if (All_Intersections ((OBJECT *) Local_Shape, Ray, Depth_Queue))
  87.            Intersection_Found = TRUE;
  88.  
  89.    return (Intersection_Found);
  90.    }
  91.  
  92. int All_CSG_Intersect_Intersections (Object, Ray, Depth_Queue)
  93.    OBJECT *Object;
  94.    RAY *Ray;
  95.    PRIOQ *Depth_Queue;
  96.    {
  97.    int Intersection_Found, Any_Intersection_Found;
  98.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  99.    SHAPE *Local_Shape, *Shape2;
  100.    PRIOQ *Local_Depth_Queue;
  101.    INTERSECTION *Local_Intersection;
  102.  
  103.    Local_Depth_Queue = pq_new (128);
  104.  
  105.    Any_Intersection_Found = FALSE;
  106.  
  107.    for (Local_Shape = Shape -> Shapes ;
  108.         Local_Shape != NULL ;
  109.         Local_Shape = Local_Shape -> Next_Object) {
  110.  
  111.       All_Intersections ((OBJECT *) Local_Shape, Ray, Local_Depth_Queue);
  112.  
  113.       for (Local_Intersection = pq_get_highest (Local_Depth_Queue);
  114.            Local_Intersection != NULL ;
  115.            pq_delete_highest (Local_Depth_Queue),
  116.            Local_Intersection = pq_get_highest (Local_Depth_Queue)) {
  117.  
  118.          Intersection_Found = TRUE;
  119.  
  120.          for (Shape2 = Shape -> Shapes;
  121.               Shape2 != NULL ;
  122.               Shape2 = Shape2 -> Next_Object)
  123.  
  124.             if (Shape2 != Local_Shape)
  125.                if (!Inside (&Local_Intersection->Point, (OBJECT *) Shape2)) {
  126.                  Intersection_Found = FALSE;
  127.                  break;
  128.                  }
  129.  
  130.          if (Intersection_Found) {
  131.             pq_add (Depth_Queue, Local_Intersection);
  132.             Any_Intersection_Found = TRUE;
  133.             }
  134.          }
  135.       }
  136.  
  137.    pq_free (Local_Depth_Queue);
  138.  
  139.    return (Any_Intersection_Found);
  140.    }
  141.  
  142. int Inside_CSG_Union (Test_Point, Object)
  143.    VECTOR *Test_Point;
  144.    OBJECT *Object;
  145.    {
  146.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  147.    SHAPE *Local_Shape;
  148.  
  149.    for (Local_Shape = Shape -> Shapes ;
  150.         Local_Shape != NULL ;
  151.         Local_Shape = Local_Shape -> Next_Object)
  152.  
  153.       if (Inside (Test_Point, (OBJECT *) Local_Shape))
  154.          return (TRUE);
  155.    return (FALSE);
  156.    }
  157.  
  158. int Inside_CSG_Intersection (Test_Point, Object)
  159.    OBJECT *Object;
  160.    VECTOR *Test_Point;
  161.    {
  162.    SHAPE *Local_Shape;
  163.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  164.  
  165.    for (Local_Shape = Shape -> Shapes ;
  166.         Local_Shape != NULL ;
  167.         Local_Shape = Local_Shape -> Next_Object)
  168.  
  169.       if (!Inside (Test_Point, (OBJECT *) Local_Shape))
  170.           return (FALSE);
  171.  
  172.    return (TRUE);
  173.    }
  174.  
  175. void *Copy_CSG (Object)
  176.    OBJECT *Object;
  177.    {
  178.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  179.    CSG_SHAPE *New_Shape;
  180.    SHAPE *Local_Shape, *Copied_Shape;
  181.  
  182.    New_Shape = Get_CSG_Shape ();
  183.    New_Shape->Methods = Shape->Methods;
  184.    New_Shape->Type = Shape->Type;
  185.    New_Shape -> Next_Object = NULL;
  186.    New_Shape -> Shapes = NULL;
  187.  
  188.    for (Local_Shape = Shape -> Shapes;
  189.         Local_Shape != NULL ;
  190.         Local_Shape = Local_Shape -> Next_Object) {
  191.  
  192.       Copied_Shape = (SHAPE *) Copy ((OBJECT *) Local_Shape);
  193.       Link ((OBJECT *) Copied_Shape,
  194.             (OBJECT **) &(Copied_Shape -> Next_Object),
  195.             (OBJECT **) &(New_Shape -> Shapes));
  196.       }
  197.    return (New_Shape);
  198.    }
  199.  
  200. void Translate_CSG (Object, Vector)
  201.    OBJECT *Object;
  202.    VECTOR *Vector;
  203.    {
  204.    SHAPE *Local_Shape;
  205.  
  206.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  207.         Local_Shape != NULL ;
  208.         Local_Shape = Local_Shape -> Next_Object)
  209.  
  210.       Translate ((OBJECT *) Local_Shape, Vector);   
  211.    }
  212.  
  213. void Rotate_CSG (Object, Vector)
  214.    OBJECT *Object;
  215.    VECTOR *Vector;
  216.    {
  217.    SHAPE *Local_Shape;
  218.  
  219.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  220.         Local_Shape != NULL ;
  221.         Local_Shape = Local_Shape -> Next_Object)
  222.  
  223.       Rotate ((OBJECT *) Local_Shape, Vector);   
  224.    }
  225.  
  226. void Scale_CSG (Object, Vector)
  227.    OBJECT *Object;
  228.    VECTOR *Vector;
  229.    {
  230.    SHAPE *Local_Shape;
  231.  
  232.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  233.         Local_Shape != NULL ;
  234.         Local_Shape = Local_Shape -> Next_Object)
  235.  
  236.       Scale ((OBJECT *) Local_Shape, Vector);   
  237.    }
  238.  
  239. void Invert_CSG (Object)
  240.    OBJECT *Object;
  241.    {
  242.    SHAPE *Local_Shape;
  243.    CSG_SHAPE *Csg = (CSG_SHAPE *) Object;
  244.  
  245.    if (Csg->Type == CSG_INTERSECTION_TYPE) {
  246.       Csg->Type = CSG_UNION_TYPE;
  247.       Csg->Methods = &CSG_Union_Methods;
  248.       }
  249.    else if (Csg->Type == CSG_UNION_TYPE) {
  250.       Csg->Type = CSG_INTERSECTION_TYPE;
  251.       Csg->Methods = &CSG_Intersection_Methods;
  252.       }
  253.  
  254.    for (Local_Shape = Csg -> Shapes;
  255.         Local_Shape != NULL ;
  256.         Local_Shape = Local_Shape -> Next_Object)
  257.  
  258.       Invert ((OBJECT *) Local_Shape);   
  259.    }
  260.  
  261. void Set_CSG_Parents (Shape, Object)
  262.    CSG_SHAPE *Shape;
  263.    OBJECT *Object;
  264.    {
  265.    SHAPE *Local_Shape;
  266.  
  267.    for (Local_Shape = Shape -> Shapes;
  268.         Local_Shape != NULL ;
  269.         Local_Shape = Local_Shape -> Next_Object) {
  270.  
  271.       Local_Shape->Parent_Object = Object;
  272.       if ((Local_Shape->Type == CSG_UNION_TYPE) ||
  273.           (Local_Shape->Type == CSG_INTERSECTION_TYPE))
  274.          Set_CSG_Parents((CSG_SHAPE *)Local_Shape, Object);
  275.       }
  276.    }
  277.  
  278.